package com.hehao.java_basic.algorithm.数据结构;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.test.context.junit4.SpringRunner;

import java.util.Arrays;

import static java.util.Arrays.binarySearch;

/**
 * @author Damon
 * @date 2023/2/14
 */
@SpringBootTest(classes = ArrayTest.class)
@RunWith(SpringRunner.class)
public class ArrayTest {

    /**
     * 移动0的元素到数组末尾
     */
    @Test
    public void moveZeros() {
        final int[] nums = {0, 1, 0, 3, 12};
        int index = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[index++] = num;
            }
        }
        while (index < nums.length) {
            nums[index++] = 0;
        }
        System.out.println("===============" + Arrays.toString(nums));
    }

    /**
     * 重塑矩阵
     */
    @Test
    public void reshapeMatrix() {
        final int[][] matrixNums = {{1, 2}, {3, 4}};
        int row = 1;
        int column = 4;
        int[][] reshape = reshape(matrixNums, row, column);
        System.out.println("=======二维矩阵->一维数组========" + Arrays.toString(reshape));
    }

    private static int[][] reshape(int[][] nums, int row, int column) {
        int m = nums.length;
        int n = nums[0].length;
        if (m * n != row * column) {
            return nums;
        }
        int[][] reshapeNums = new int[row][column];
        int index = 0;
        for (int i = 0; i < row; row++) {
            for (int j = 0; j < column; column++) {
                reshapeNums[i][j] = nums[index / n][index % n];
                index++;
            }
        }
        return reshapeNums;
    }

    /**
     * 二分查找
     */
    @Test
    public void binarySearchTest() {
        int[] array = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}; // 有序数组
        int target = 3;
        int result = this.binarySearch(array, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }

    private int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = array[mid];
            if (midValue == target) {
                return mid;
            } else if (midValue < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}
